package java学习.leetcode.editor.cn;
/**
 * @author 刘世锦
 * 2022-09-23 15:03:12	 当前时间
 */
//给你一个二进制字符串数组 strs 和两个整数 m 和 n 。 
//
// 
// 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。 
//
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
//输出：4
//解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
//其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 
//n 的值 3 。
// 

import java学习.算法.测试.arr;

/**
 *   0 1
 * 0 1 1
 * 1 3 1
 * 2 2 4
 * 3 0 1
 * 4 1 0
 *
 */
// 示例 2： 
//
// 
//输入：strs = ["10", "0", "1"], m = 1, n = 1
//输出：2
//解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= strs.length <= 600 
// 1 <= strs[i].length <= 100 
// strs[i] 仅由 '0' 和 '1' 组成 
// 1 <= m, n <= 100 
// 
// Related Topics 数组 字符串 动态规划 
// 👍 798 👎 0

public class 一和零{
	public static void main(String[] args) {
		Solution solution = new 一和零().new Solution();
		String[] strs = {"10", "0001", "111001", "1", "0"};
		int m = 5, n = 3;
		System.out.println(solution.findMaxForm(strs,m,n));
		System.out.println(-5&6); //28
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
//    	记录 每个字符串的 0,1 个数
		int [][] arr = new int[strs.length][2];
		int one,zero;
		for (int i = 0; i < strs.length; i++) {
			  one = 0;
			  zero = 0;
			for (int j= 0; j < strs[i].length(); j++) {
				if (strs[i].charAt(j)=='0'){
					zero++;
				}	else {
					one++;
				}
			}
			arr[i][0] = zero;
			arr[i][1] = one;
		}
//		for (int i = 0; i < arr.length; i++) {
//				System.out.print(arr[i][0]+" "+arr[i][1]);
//			System.out.println();
//		}
		/**
		 *    0 1
		 *
		 * 0  1 1
		 * 1  3 1
		 * 2  2 4
		 * 3  0 1
		 * 4  1 0
		 * 该子集中 最多 有 m 个 0 和 n 个 1 。
		 */

		/**
		 * 	1. 定义： 背包容量为 m个0，n个1 可包含strs的最大子集数
		 *  2. dp[j][k] = Math.max(  dp[j][k] ,      dp[j-n0][k-n1]+1);
		 *                           不取该字符串       取该字符串 ; +1是因为取该字符串作为子集，子集数+1
		 *  3. 多个01背包
		 *  4. 初始化：背包容量为0 子集数必为零
		 *  5. 01背包：先遍历物品，在逆序遍历背包 (01一维数组)
		 */
		int [][] dp = new int[m+1][n+1];
		for (int i = 0; i < arr.length; i++) {
			int n0 = arr[i][0];
			int n1 = arr[i][1];
//			之前都是 一个 01背包，这块可以理解为两个 01背包
			for(int j = m;j>=n0;j--){
				for (int k = n;k>=n1;k--){
					dp[j][k] = Math.max(dp[j][k] ,dp[j-n0][k-n1]+1);
				}
			}
		}
		return dp[m][n];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
